/**
 * 01背包问题
 * 2017.4.14 By 杨帆
 */

#include <iostream>
#include <iomanip>


using namespace std;

class wv
{
public:
    int w = 0; //价值
    int v = 0; //占用空间
    wv(int we, int vv) : w(we), v(vv)
    {
    }
};


/**
 * 对物品进行排序
 * @param wMap 传入的数组 表示物品
 * @param sMap 排序后 物品清单
 */
void Sort(wv *ww, int n)
{
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n - i - 1; ++j)
        {
            if (ww[j].v > ww[j + 1].v)
            {
                wv t = ww[j];
                ww[j] = ww[j + 1];
                ww[j + 1] = t;
            }
        }
    }
}

/**
 * 挑选物品
 * @param ww 物品清单（已排序）
 * @param re 选中的结果
 * @return 最大价值
 */
int Select(wv *ww, int n, int remainSpace)
{
    int right = n;
    for (int i = 0; i < right; ++i)
    {
        if (ww[i].v > remainSpace)
        {
            right = i;
            break;
        }
    }
    int max = 0;
    int csp = remainSpace + 1;
    int f[right][csp];
    for (int i = 0; i < right; ++i)
        for (int v = 0; v < csp; ++v)
            f[i][v] = 0;

    for (int i = 0; i < right; ++i)
    {
        for (int v = 0; v < csp; ++v)
        {
            if (v < ww[i].v)
            {
                if (i == 0)
                    f[i][v] = 0;
                else
                    f[i][v] = f[i - 1][v];
            }
            else
            {
                if (i == 0)
                    f[i][v] = ww[i].w;
                else
                    f[i][v] = f[i - 1][v] > f[i - 1][v - ww[i].v] + ww[i].w
                              ? f[i - 1][v]
                              : f[i - 1][v - ww[i].v] + ww[i].w;
            }
            max = max > f[i][v] ? max : f[i][v];
        }
    }

    return max;
}


int main()
{
    wv w[] = {wv(10, 23), wv(7, 14), wv(12, 34), wv(11, 4), wv(33, 25)};
    Sort(w, 5);
    for (int i = 0; i < 5; ++i)
    {
        cout << "体积 => " << setw(3) << w[i].v << " : 价值 => " << setw(3) << w[i].w << endl;
    }

    cout << "获得的最大价值 : " << Select(w, 5, 29) << endl;

    return 0;
}